Hit of the Season

Memory limit: 256 MB

Byteotian Printing Factory (BPF) has received a large production order for striped wallpaper. Striped wallpaper is the hit of the season in interior design. Each wallpaper has equal width coloured vertical stripes coloured red, green and blue. BPF is to take care of the design and printing of wallpapers. It is assumed the customer would describe the colour of certain wallpaper stripes. In the case of other stripe colours, the customer allowed BPF a complete freedom.

BPF uses matrices to print a certain number of consecutive bars on the wallpaper. The matrix has a specific colour of each of the printed stripes. The matrix may be shorter than the entire wallpaper. With each application, the matrix stripes must match and overlay the wallpaper stripes; then printing of all the matrix stripes takes place. In this way, a single wallpaper stripe can be printed over more than once. In case a given stripe is printed over using different colours, the final colour is a blend of these colours. The matrix prints only in one orientation and must not in any way be rotated.

BPF employees, irrespective of their sense of aesthetics, would primarily like to design the shortest possible matrix that will allow printing the entire wallpaper. They must bear in mind that in the case of stripes defined by the customer they must use pure colour, without any addition of any other colour. In other words, for each matrix application printing over such a single-colour stripe, the matrix stripe colour must be exactly as defined by the client. No stripe on the wallpaper can remain colourless.

Input

The first line of input contains one integer () denoting the number of test cases. Each of the next lines describes a single test case and includes a string of upper-case letters R, G, B and asterisks (*), specifying the desired wallpaper appearance. The letters denote the colour of the stripes, and the asterisks mark the stripes, the colour of which has not been specified by the client. A string is not empty, it consists of a maximum of 3000 characters and contains at most 19 asterisks.

Output

For each of the test cases your program should output one line containing a string of characters R, G, B: minimum length matrix that allows printing the desired wallpaper. If for a given test case, there are many correct solutions, your program should output any of them.

Example

For the input data:

1
RRG*R*BRR**B

the correct result is:

RRGB

Task authors: Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen.